The present invention relates to an improved system for addressing flash memories and, more particularly, to an address translation in a flash file system that reduces the number of bits required for virtual addressing.
Flash devices include electrically erasable and programmable read-only memories (EEPROMs) made of flash-type, floating-gate transistors and are non-volatile memories similar in functionality and performance to EPROM memories, with an additional functionality that allows an in-circuit, programmable operation to erase portions of the memory. Flash devices have the advantage of being relatively inexpensive and requiring relatively little power as compared to traditional magnetic storage disks. However, flash devices have certain limitations that make using them at the physical address level a bit of a problem. In a flash device, it is not practical to rewrite a previously written area of the memory without a prior erase of the area, i.e. flash cells must be erased (e.g programmed to “one”) before they can be programmed again. Erasing can only be done for relatively large groups of cells usually called “erase blocks” (typically of size 16 to 128 Kbytes in current commercial NAND devices, and of larger size in NOR devices). Therefore updating the contents of a single byte or even of a chunk of 1 kilobytes requires “housekeeping” operations—parts of the erase block that are not updated must first be moved elsewhere so they will be preserved during erasing, and then moved back into place.
Furthermore, some of the blocks of the device are “bad blocks”, which are not reliable and their use should be avoided. Blocks are declared as “bad blocks” either by the manufacturer when initially testing the device, or by application software when detecting the failure of the blocks during use of the device in the field.
To overcome these limitations of the background art, a Flash File System (FFS) was disclosed in U.S. Pat. No. 5,404,485, which is assigned to the assignee of the present application and is hereby incorporated by reference as if fully set forth herein. FFS provides a system of data storage and manipulation on flash devices which allows these devices to emulate magnetic disks. In the existing art, applications or operating systems interact with the flash storage subsystem not using physical addresses but rather virtual addresses. There is an intermediary layer between the software application and the physical device that provides a mapping from the virtual addresses into the physical addresses. While the software may view the storage system as having a contiguous defect-free medium that can be read or written randomly with no limitations, the physical addressing scheme has “holes” in its address range (due to bad blocks, for example), and pieces of data that are adjacent to each other in the virtual address range might be greatly separated in the physical address range. The intermediary layer that does the mapping described above may be a software driver running on the same CPU on which the applications run. Alternatively, the intermediary layer may be embedded within a controller that controls the flash device and serves as the interface point for the main CPU of the host computer when the host computer accesses the storage. This is for example the situation in removable memory cards such as secure digital (SD) cards or multimedia cards (MMC), where the card has an on-board controller running a firmware program that among other functions, implements the type of mapping described above.
Software or firmware implementations doing such address mappings are typically called “flash management systems” or “flash file systems”. The latter term is a misnomer, as the implementations do not necessarily support “files”, in the sense that files are used in operating systems or personal computers, but rather support block device interfaces similar to those exported by hard disk software drivers. Still, the term is commonly used, and “flash file system” and “flash management system” are used herein interchangeably.
Other prior art systems that implement virtual-to-physical address mapping can be found in U.S. Pat. No. 5,937,425 disclosed by Ban and U.S. Pat. No. 6,591,330 disclosed by Lasser, both of which are incorporated by reference for all purposes as if fully set forth herein.
In U.S. Pat. No. 5,937,425, which is particularly suitable for NAND-type flash devices, the mapping is done as follows referring to FIG. 1 (prior art). Physical address space 13 is composed of units 111 that are actually the erase blocks i.e. the smallest chunks that can be erased. Each physical unit 111 contains one or more physical pages 113, where a page is the smallest chunk that can be written. A virtual address space 11 is composed of virtual units 121 that have the same size as the physical units. Each virtual unit contains one or more virtual pages 123, having the same size as physical pages 113. When a virtual address is provided by an application, for reading or writing, the virtual unit number to which that address belongs is extracted from the virtual address. There is a mapping that assigns to each virtual unit 121 either one physical unit 111 or a chain of more than one physical unit 111. Then physical page 113 corresponding to requested virtual page 123 within virtual unit 121 is located within the corresponding physical unit(s) 111, using a “local” mapping rule that relates virtual pages 123 to physical pages 113, or using control information stored with physical pages 113.
One of the advantages of the methods disclosed in U.S. Pat. No. 5,937,425 is that as the main mapping is done over units rather than pages, the translation tables become much smaller, as there are much fewer units than pages. Another advantage is write performance improvement that results from being able to assign more than one physical unit 111 to one virtual unit 121.
For a few reasons, the typical size of the valid virtual address range is slightly smaller than the size of the mapped-to physical address range. The reasons include:
(1) Virtual space 11 cannot include bad blocks and therefore virtual space 11 is “squeezed” to exclude bad blocks from its address range, while bad blocks may exist in physical space 13.
(2) For a flash file system supporting a one-to-many mapping, as disclosed in U.S. Pat. No. 5,937,425, virtual space 11 must be smaller than physical space 13.
In prior art flash management systems the number of bits required for representing a virtual address is the same as the number of bits required for representing a physical address. For example suppose a NAND flash device is composed of 1,024 physical units 111 each containing 32 pages 113 of 512 bytes (ignoring “extra” bytes in NAND devices that typically do not store user data but system information such as error correction codes). On the physical level the bytes address range is from zero to 16 megabytes minus one, requiring 24 bits for full representation. Using the methods of U.S. 5,937,425 that directly map only the unit addresses, we have 1,024 physical units 111 and requiring 10 bits. Assuming the virtual space 11 is smaller by 24 units, we get 1,000 virtual units 121 each containing 32 pages 123 of 512 bytes each. The number of bits for representing the full byte address is again 24, and the number of bits required for representing the number of virtual units is still 10. It is sometimes very desirable to have the number of bits required for representing a virtual address to be as low as possible. Both flash file systems and software applications keep addresses in tables and in various data structures, and the more bits an address requires the more RAM memory is spent.
There is thus a need for, and it would be highly advantageous to have a method for virtual to physical address translation in a flash file system that reduces the number of bits required for virtual addressing.